﻿// 遗传算法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define popSize 10000
#define maxGen 80
#define Pc 0.7
#define Pm 0.1
#define Pa 1.1
#define Pb 0.2
int chromSize = 0;



class indivadual
{
public:
    indivadual() { chrom.resize(chromSize); };
    vector<int> chrom;
    double fitness;
    bool operator ==(const indivadual& i)
    {
        int t = 0;
        for (t = 0; t < chromSize; t++)
        {
            if (find(chrom.begin(), chrom.end(), i.chrom[t]) == chrom.end())
            {
                return false;
            }
        }
        return true;

    }
};

class Evalution
{
private:
    vector<indivadual> Population;

    indivadual Best;
    int BestIndex;
    indivadual Worst;
    int WorstIndex;
    indivadual HistoryBest;
    double avg;
    void Initialization();
    void SelectPop();
    void CrossPop();
    void VaryPop();
    void Optimizepop() {};
public:
    Evalution();
    void Evalute();
    void NextPopulation();
    void OutPut();
    vector<indivadual> good;
    int gen;
};
Evalution::Evalution()
{
    Initialization();
}
void Evalution::Initialization()
{
    int i = 0, j = 0;
    Population.resize(popSize);
    for (i = 0; i < popSize; i++)
    {
        j = 0;
        while (j < chromSize)
        {
            int n = rand();
            n = n % (chromSize * chromSize);


            if (find(Population[i].chrom.begin(), Population[i].chrom.end(), n) == Population[i].chrom.end() || n == 0)
            {
                Population[i].chrom[j] = n;
                j++;
            }
        } //发的
    }
    Worst = Best = Population[0];
    WorstIndex = BestIndex = 0;
    gen = 0;
    avg = 0;
    Best.fitness = 0;
    Worst.fitness = 0;
}

void Evalution::Evalute()
{
    int index = 0;
    for (index = 0; index < popSize; index++)
    {
        //适应值最大为1
        Population[index].fitness = 1;
        //横坐标
        vector<int> x;
        x.resize(chromSize);
        //纵坐标
        vector<int> y;
        y.resize(chromSize);
        int i = 0, j = 0, q = 0, p = 0;
        for (j = 0; j < chromSize; j++)
        {
            p = Population[index].chrom[j] / chromSize;
            x[j] = p;
            q = Population[index].chrom[j] % chromSize;
            y[j] = q;
        }
        for (i = 0; i < chromSize; i++)
        {
            for (j = i + 1; j < chromSize; j++)
            {
                if (x[i] == x[j])
                {
                    Population[index].fitness++;
                }
            }
        }
        for (i = 0; i < chromSize; i++)
        {
            for (j = i + 1; j < chromSize; j++)
            {
                if (y[i] == y[j])
                {
                    Population[index].fitness++;
                }
            }
        }
        //取交叉数目的倒数为适应值
        Population[index].fitness = 1 / Population[index].fitness;
        if (Population[index].fitness == 1 && find(good.begin(), good.end(), Population[index]) == good.end())
        {
            good.push_back(Population[index]);
        }
        //更新当代最佳
        if (Best.fitness < Population[i].fitness)
        {
            Best = Population[index];
            BestIndex = index;
        }
        //更新当代最差
        if (Worst.fitness > Population[index].fitness)
        {
            Worst = Population[index];
            WorstIndex = index;
        }
    }
    //更新历史最佳
    if (HistoryBest.fitness < Best.fitness)
    {
        HistoryBest = Best;
    }
    //计算平均值
    for (index = 0; index < popSize; index++)
    {
        avg += Population[index].fitness;
    }
    avg /= popSize;
    //代数更替
    gen++;

}
void Evalution::NextPopulation()
{
    //选择
    SelectPop();
    //交叉
    CrossPop();
    //变异
    VaryPop();
    //评价
    Evalute();
    //优化
    Optimizepop();
}

//输出
void Evalution::OutPut()
{

    cout << "当前代数" << gen << "   平均值" << avg << "   最好个体适应值" << Best.fitness << "最好个体基因";
    int i = 0;
    for (i = 0; i < chromSize; i++)
    {
        cout << Best.chrom[i] << "  ";
    }
    cout << endl;
}

//sort函数的辅助函数
bool compare(indivadual a, indivadual b)
{
    if (a.fitness > b.fitness)
    {
        return true;
    }
    if (a.fitness > b.fitness)
    {
        return false;
    }
    return false;
}

//线性排名选择
void Evalution::SelectPop()
{
    sort(Population.begin(), Population.end(), compare);
    double p[popSize], selection[popSize];
    indivadual newPopulation[popSize];
    double FitSum = 0;
    int i = 0, j = 0, index = 0, popindex = 0;
    //计算分配概率
    for (i = 0; i < popSize; i++)
    {
        j = i + 1;
        p[i] = (Pa - Pb / (j + 1)) / j;
    }
    //求分配概率的总和
    for (index = 0; index < popSize; index++)
    {
        FitSum += p[index];
    }

    //确定轮盘分布
    for (index = 0; index < popSize; index++)
    {
        selection[index] = p[index] / FitSum;
    }
    for (index = 1; index < popSize; index++)
    {
        selection[index] = selection[index] + selection[index - 1];
    }
    //用轮盘进行随机选取，形成新的种群
    for (popindex = 0; popindex < popSize; popindex++)
    {
        double n = (rand() % 100) / 100.0;
        index = 0;
        while (n > selection[index])
            index++;
        newPopulation[popindex] = Population[index];
    }
    //将刚产生的群体替换为系统的群体
    for (index = 0; index < popSize; index++)
    {
        Population[index] = newPopulation[index];
    }
}

//杂交算子,离散杂交
void Evalution::CrossPop()
{
    int index = 0, position = 0, i = 0, temp = 0, t = 0;
    for (; index < popSize; index++)
    {
        indivadual temp;
        int r = rand() % popSize;
        temp = Population[index];
        Population[index] = Population[r];
        Population[r] = temp;
    }
    for (index = 0; index < popSize; index += 2)
    {
        t = rand() % 1000 / 1000.0;
        if (t < Pc)
        {
            position = rand() % chromSize;
            for (i = position + 1; i < chromSize; i++)
            {
                temp = Population[index + 1].chrom[i];
                Population[index + 1].chrom[i] = Population[index].chrom[i];
                Population[index].chrom[i] = temp;

            }

        }

    }
}


//变异算子,自适应性变异
void Evalution::VaryPop()
{
    int i = 0, j = 0, up = chromSize * chromSize - 1, down = 0;
    for (i = 0; i < popSize; i++)
    {
        for (j = 0; j < chromSize; j++)
        {
            double r = rand() % 1000 / 1000.0;
            if (r < Pm)
            {
                double t = 1 - Population[i].fitness * 0.9999 / Best.fitness;
                //突变区间
                int u = (1 - pow(r, pow(t, 2))) * (up - Population[i].chrom[j]);

                if (u > up)
                {
                    u = up;
                }
                if (u < down)
                {
                    u = down;
                }
                int l = (1 - pow(r, pow(t, 2))) * (Population[i].chrom[j] - down);
                if (l > up)
                {
                    l = up;
                }
                if (l < down)
                {
                    l = down;
                }

                int p = rand() % 2;
                if (p == 0)
                {
                    Population[i].chrom[j] = u;
                }
                else
                    Population[i].chrom[j] = l;
            }
        }
    }
}

int main()
{
    cout << "n=";
    int n = 0;
    cin >> n;
    chromSize = n;
    Evalution eva;
    eva.Evalute();
    eva.OutPut();
    while (eva.gen < maxGen)
    {
        eva.NextPopulation();
        eva.OutPut();
    }
    int i = 0, j = 0;
    cout << "解共有" << eva.good.size() << endl;
    for (i = 0; i < eva.good.size(); i++)
    {
        for (j = 0; j < chromSize; j++)
        {
            cout << eva.good[i].chrom[j] << "   ";
        }
        cout << endl;

    }
}


// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
